class Solution {
public:
    int takeAttendance(vector<int>& records) {
        // 二分查找算法
        // 例子: [0, 1, 2, 3, 5]
        //        0  1  2  3  4
        // 可以发现最后一个元素下标值不是和对应值一样，所以4就是结果
        int left = 0, right = records.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(records[mid] == mid)
                left = mid + 1;
            else 
                right = mid;
        }
        return records[left] == left ? left + 1 : left;

        // 高斯求和方法
        // int n = records.size(), sum = 0, ans = 0;
        // for(int i = 0; i < n; i++)
        //     sum += records[i];
        // return ((0 + n) * (n + 1)) / 2 - sum;


        // 哈希表
        // unordered_set<int> s;
        // for(auto &e : records)
        //     s.insert(e);
        // for(int i = 0; i <= records.size(); i++)
        // {
        //     if(s.find(i) == s.end())
        //         return i;
        // }
        // return 0;
    }
};